package DifficultPractice;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class Demo52 {
//	52. N皇后 II
//	n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
//
//	给你一个整数 n ，返回 n 皇后问题 不同的解决方案的数量。
	private int ans = 0;
	
	public int totalNQueens(int n) {
		char[][] board = new char[n][n];
		
		for(int i=0; i<n; i++) {
			Arrays.fill(board[i], '.');
		}
		
		backTrack(board, 0, n);
		
		return ans;
    }
	
	private void backTrack(char[][] board, int row, int n) {
		if(row == n) {
			ans += 1;
			return;
		}
		
		for(int col=0; col<n; col++) {
			if(isInValid(board, row, col)) {
				continue;
			}
			
			//选择放row col 这个位置
			board[row][col] = 'Q';
			
			backTrack(board, row+1, n);
			
			//撤销这次选择  重新再选
			board[row][col] = '.';
		}
		
	}

	private boolean isInValid(char[][] board, int row, int col) {
		
		for(int i=0; i<board.length; i++) {
			if(i == col)	continue;
			
			if(board[row][i] == 'Q')
				return true;
		}
		
		for(int i=0; i<board.length; i++) {
			if(i == row)	continue;
			
			if(board[i][col] == 'Q')
				return true;
		}
		
		for(int i=row-1, j=col-1; i>=0 && j>=0; i--,j--) {
			if(board[i][j] == 'Q')
				return true;
		}
		for(int i=row+1, j=col+1; i<board.length && j<board.length; i++,j++) {
			if(board[i][j] == 'Q')
				return true;
		}
		
		for(int i=row-1, j=col+1; i>=0 && j<board.length; i--,j++) {
			if(board[i][j] == 'Q')
				return true;
		}
		for(int i=row+1, j=col-1; i<board.length && j>=0; i++,j--) {
			if(board[i][j] == 'Q')
				return true;
		}
		
		
		return false;
	}

}
